package sortAlgorithm;

public class ShellSort {
    public static void main(String[] args) {
        int[] a = {9, 6, 4, 3, 1};
        shellSort(a);
        printArray(a);
    }

    public static void shellSort(int[] array) {
        // 不断地缩小增量
        for (int interval = array.length / 2; interval > 0; interval /= 2) {
            // 一趟一个增量，用增量来分组，组内进行插入排序
            // 插排
            for (int i = interval; i < array.length; i++) {
                int target = array[i];
                int j = i - interval;    //target组内前一个元素
                // 往自己的组里，进行插入排序
                while (j > -1 && array[j] > target) {//前一个元素存在，且大于target
                    array[j + interval] = array[j];
                    j -= interval;
                }
                array[j + interval] = target;
            }
        }
    }

    public static void printArray(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length - 1; i++) {
            System.out.print(array[i] + ",");
        }
        System.out.println(array[array.length - 1] + "]");
    }
}
